{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #生物进化录"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evolutionaryRecord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生物进化录"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在永恒之森中，存在着一本生物进化录，以 **一个树形结构** 记载了所有生物的演化过程。经过观察并整理了各节点间的关系，`parents[i]` 表示编号 `i` 节点的父节点编号(根节点的父节点为 `-1`)。\n",
    "\n",
    "为了探索和记录其中的演化规律，队伍中的炼金术师提出了一种方法，可以以字符串的形式将其复刻下来，规则如下：\n",
    "- 初始只有一个根节点，表示演化的起点，依次记录 `01` 字符串中的字符，\n",
    "- 如果记录 `0`，则在当前节点下添加一个子节点，并将指针指向新添加的子节点；\n",
    "- 如果记录 `1`，则将指针回退到当前节点的父节点处。\n",
    "\n",
    "现在需要应用上述的记录方法，复刻下它的演化过程。请返回能够复刻演化过程的字符串中， **字典序最小** 的 `01` 字符串。\n",
    "\n",
    "**注意：**\n",
    "- 节点指针最终可以停在任何节点上，不一定要回到根节点。\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`parents = [-1,0,0,2]`\n",
    ">\n",
    "> 输出：`\"00110\"`\n",
    ">\n",
    ">解释：树结构如下图所示，共存在 2 种记录方案：\n",
    ">第 1 种方案为：0(记录编号 1 的节点) -> 1(回退至节点 0) -> 0(记录编号 2 的节点) -> 0((记录编号 3 的节点))\n",
    ">第 2 种方案为：0(记录编号 2 的节点) -> 0(记录编号 3 的节点) -> 1(回退至节点 2) -> 1(回退至节点 0) -> 0(记录编号 1 的节点)\n",
    ">返回字典序更小的 `\"00110\"`\n",
    "![image.png](https://pic.leetcode.cn/1682319485-cRVudI-image.png){:width=120px}![进化 (3).gif](https://pic.leetcode.cn/1682412701-waHdnm-%E8%BF%9B%E5%8C%96%20\\(3\\).gif){:width=320px}\n",
    "\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`parents = [-1,0,0,1,2,2]`\n",
    ">\n",
    "> 输出：`\"00101100\"`\n",
    "\n",
    "**提示：**\n",
    "\n",
    "- `1 <= parents.length <= 10^4`\n",
    "- `-1 <= parents[i] < i` (即父节点编号小于子节点)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [qoQAMX](https://leetcode.cn/problems/qoQAMX/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [qoQAMX](https://leetcode.cn/problems/qoQAMX/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,0,2]', '[-1,0,0,1,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        children = {}\n",
    "        for i, p in enumerate(parents):\n",
    "            c = children.get(p, [])\n",
    "            c.append(i)\n",
    "            children[p] = c\n",
    "            if p == -1:\n",
    "                root = i\n",
    "        def circuit(start):\n",
    "            routes = []\n",
    "            for child in children.get(start, []):\n",
    "                routes.append('0'+circuit(child)+'1')\n",
    "            routes.sort()\n",
    "            return ''.join(routes)\n",
    "        ret = circuit(root)\n",
    "        while ret != '' and ret[-1] == '1':\n",
    "            ret = ret[:-1]\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        nodeInfo = {}\n",
    "        for child, node in enumerate(parents):\n",
    "            if node == -1:\n",
    "                continue\n",
    "            if node not in nodeInfo:\n",
    "                nodeInfo[node] = []\n",
    "            nodeInfo[node].append(child)\n",
    "\n",
    "        def dfs(node, nodes):\n",
    "            if node not in nodes:\n",
    "                return '01'\n",
    "            cur = [dfs(i, nodes) for i in nodes[node]]\n",
    "            cur.sort()\n",
    "            return '0' + ''.join(cur) + '1'\n",
    "        ans = dfs(0, nodeInfo)\n",
    "        return ans[1:].rstrip('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        g = [[] for _ in range(len(parents))]\n",
    "        for node, parent in enumerate(parents[1:], 1): g[parent].append(node)\n",
    "        dfs = lambda node: f\"0{''.join(sorted(map(dfs, g[node])))}1\"\n",
    "        return dfs(0)[1:].rstrip(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        g = [[] for _ in range(len(parents))]\n",
    "        for n, p in enumerate(parents[1:], 1):\n",
    "            g[p].append(n)\n",
    "        dfs = lambda x: f\"0{''.join(sorted(map(dfs, g[x])))}1\"\n",
    "        return dfs(0)[1:].rstrip(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        g = {}\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1: continue\n",
    "            if p in g:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                g[p] = [i]\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x not in g:\n",
    "                return ''\n",
    "            \n",
    "            nxt = []\n",
    "            for y in g[x]:\n",
    "                nxt.append('0'+dfs(y)+'1')\n",
    "            return ''.join(sorted(nxt))\n",
    "\n",
    "        return dfs(0).rstrip('1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "\n",
    "        def search(pos_):\n",
    "            if pos_ not in kid_dict.keys():\n",
    "                return \"\"\n",
    "            my_kids = kid_dict[pos_]\n",
    "            substr_list = []\n",
    "            for kid in my_kids:\n",
    "                substr_list.append(f\"0{search(kid)}1\")\n",
    "            substr_list.sort()\n",
    "            rs = \"\".join(substr_list)\n",
    "            return rs\n",
    "        \n",
    "        kid_dict = dict()\n",
    "        for index,value in enumerate(parents):\n",
    "            if value>=0:\n",
    "                if value not in kid_dict.keys():\n",
    "                    kid_dict[value] = []\n",
    "                kid_dict[value].append(index)\n",
    "        # print(kid_dict)\n",
    "\n",
    "        ans = search(0)\n",
    "        while len(ans) > 0 and ans[-1] == \"1\":\n",
    "            ans = ans[:-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        g = {}\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1: continue\n",
    "            if p in g:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                g[p] = [i]\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x not in g:\n",
    "                return 0, ''\n",
    "            \n",
    "            nxt = []\n",
    "            for y in g[x]:\n",
    "                nd, ny = dfs(y)\n",
    "                nxt.append((nd+1, '0'+ny+'1'))\n",
    "            nxt.sort(key=lambda x: (-x[0], x[1]))\n",
    "\n",
    "            return nxt[0][0], ''.join(x for _, x in nxt)\n",
    "\n",
    "        _, ans = dfs(0)\n",
    "        n = len(ans) - 1\n",
    "        while ans and ans[n] == '1':\n",
    "            n -= 1\n",
    "        return ans[:n+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        g = {}\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1: continue\n",
    "            if p in g:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                g[p] = [i]\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x not in g:\n",
    "                return 0, ''\n",
    "            \n",
    "            nxt = []\n",
    "            for y in g[x]:\n",
    "                nd, ny = dfs(y)\n",
    "                nxt.append((nd+1, '0'+ny+'1'))\n",
    "            nxt.sort(key=lambda x: x[1])\n",
    "\n",
    "            return nxt[0][0], ''.join(x for _, x in nxt)\n",
    "\n",
    "        _, ans = dfs(0)\n",
    "        n = len(ans) - 1\n",
    "        while ans and ans[n] == '1':\n",
    "            n -= 1\n",
    "        return ans[:n+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        if len(parents) == 1:\n",
    "            return \"\"\n",
    "\n",
    "        # 记录父有哪些子\n",
    "        l_s = defaultdict(list)\n",
    "\n",
    "        for s, p in enumerate(parents):\n",
    "            l_s[p].append(s)\n",
    "\n",
    "        # 写一个节点（包括其子节点），递归\n",
    "        def dfs(p):\n",
    "            ls = l_s.get(p)\n",
    "            if not ls:\n",
    "                return \"\"\n",
    "\n",
    "            l = []\n",
    "            for s in l_s[p]:\n",
    "                l.append(\"0\" + dfs(s) + \"1\")\n",
    "\n",
    "            l.sort()\n",
    "            return \"\".join(l)\n",
    "\n",
    "        ret = dfs(0)\n",
    "\n",
    "        # 删除最后的1\n",
    "        i = len(ret) - 1\n",
    "        while ret[i] == \"1\":\n",
    "            i -= 1\n",
    "        return ret[:i + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                tree[p].append(i)\n",
    "\n",
    "        def dfs(cur: int, pre: int) -> Deque[int]:\n",
    "            sub = sorted([dfs(next, cur) for next in tree[cur] if next != pre])\n",
    "            res = deque()\n",
    "            for d in sub:\n",
    "                if len(res) > len(d):\n",
    "                    while d:\n",
    "                        res.append(d.popleft())\n",
    "                else:\n",
    "                    res, d = d, res\n",
    "                    while d:\n",
    "                        res.appendleft(d.pop())\n",
    "            res.appendleft(0)\n",
    "            res.append(1)\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, -1)\n",
    "        while res and res[-1] == 1:\n",
    "            res.pop()\n",
    "        res.popleft()\n",
    "        return \"\".join(map(str, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        d=defaultdict(list)\n",
    "        n=len(parents)\n",
    "        for i in range(n):\n",
    "            d[parents[i]].append(i)\n",
    "        \n",
    "        def dfs(i):\n",
    "            path=[]\n",
    "            for j in d[i]:\n",
    "                path.append(\"0\"+dfs(j)+\"1\")\n",
    "            path.sort()\n",
    "            return \"\".join(path)\n",
    "        return dfs(0).rstrip('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)  # 建树\n",
    "\n",
    "        def dfs(x: int) -> str:\n",
    "            a = sorted(dfs(y) for y in g[x])\n",
    "            return \"0\" + ''.join(a) + \"1\"\n",
    "        return dfs(0)[1:].rstrip('1')  # 去掉根节点以及返回根节点的路径\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(parents):\n",
    "            if x != -1:\n",
    "                g[x].append(i)\n",
    "\n",
    "        def dfs(i):\n",
    "            if len(g[i]) == 0:\n",
    "                return '01'\n",
    "            a = sorted(dfs(j) for j in g[i])\n",
    "            return '0' + ''.join(a) + '1'\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        return ans[1:].rstrip('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)  # 建立树的邻接表表示\n",
    "\n",
    "        def dfs(x: int) -> str:\n",
    "            a = sorted(dfs(y) for y in g[x])  # 对每个子节点进行深度优先搜索，并按字典序排序结果\n",
    "            return \"0\" + ''.join(a) + \"1\"  # 拼接字符串\n",
    "\n",
    "        return dfs(0)[1:].rstrip('1')  # 去掉根节点的 \"0\" 和末尾的所有 \"1\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)  # 建树\n",
    "\n",
    "        def dfs(x: int) -> str:\n",
    "            a = sorted(dfs(y) for y in g[x])\n",
    "            return \"0\" + ''.join(a) + \"1\"\n",
    "        return dfs(0)[1:].rstrip('1')  # 去掉根节点以及返回根节点的路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)  # 建树\n",
    "\n",
    "        def dfs(x: int) -> str:\n",
    "            a = sorted(dfs(y) for y in g[x])\n",
    "            return \"0\" + ''.join(a) + \"1\"\n",
    "        return dfs(0)[1:].rstrip('1')  # 去掉根节点以及返回根节点的路径\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, idx: int):\n",
    "        self.idx = idx\n",
    "        self.depth = -1\n",
    "        self.par = -1\n",
    "        self.children = []\n",
    "        self.res = \"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evolutionaryRecord(self, parents: List[int]) -> str:\n",
    "        n = len(parents)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        node_list = [Node(i) for i in range(n)]\n",
    "        root_idx = -1\n",
    "        for i, par in enumerate(parents):\n",
    "            node = node_list[i]\n",
    "            node.par = par\n",
    "\n",
    "            if par == -1:\n",
    "                root_idx = i\n",
    "            else:\n",
    "                node_list[par].children.append(i)\n",
    "\n",
    "        # 初始化\n",
    "\n",
    "        # 计算一下depth\n",
    "        tmp_nodes: List[Node] = [node_list[root_idx]]\n",
    "        depth = 0\n",
    "        while tmp_nodes:\n",
    "            new_tmp_nodes = []\n",
    "            for node in tmp_nodes:\n",
    "                node.depth = depth\n",
    "                for idx in node.children:\n",
    "                    new_tmp_nodes.append(node_list[idx])\n",
    "            tmp_nodes = new_tmp_nodes\n",
    "            depth += 1\n",
    "\n",
    "        tmp_node_list = node_list[::]\n",
    "        tmp_node_list.sort(key=lambda _node: -_node.depth)\n",
    "\n",
    "        for node in tmp_node_list:\n",
    "            res_list = []\n",
    "            for idx in node.children:\n",
    "                res_list.append(\"0\" +  node_list[idx].res + \"1\")\n",
    "            res_list.sort()\n",
    "            node.res = \"\".join(res_list)\n",
    "        res = node_list[root_idx].res\n",
    "        one_cnt = 0\n",
    "        for si in res[::-1]:\n",
    "            if si == '1':\n",
    "                one_cnt += 1\n",
    "            else:\n",
    "                break\n",
    "        return res[:-one_cnt]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
